function LinkedList() {
  // 定义初始长度为0
  this.length = 0;
  // 定义head为第一个节点
  this.head = null;
}

// + push(data)：向链表尾部添加一个新元素。
LinkedList.prototype.push = function (data) {
  const node = new Node(data);
  let current;
  if (this.head == null) {
    this.head = node;
  } else {
    // 遍历链表，找到最后一项
    current = this.head;
    while (current.next) {
      current = current.next;
    }
    // 此时current为最后一个元素，在后面追加新元素
    current.next = node;
  }
  this.length++;
}
// + insert(data, index)：向链表的特定位置插入一个新元素。
LinkedList.prototype.insert = function (data, index) {
  // 下标越界
  if (index < 0 || index > this.length) return false;
  const node = new Node(data);
  // head节点
  if (index === 0) {
    // 修改当前node的下一个节点为原来的head节点
    node.next = this.head;
    this.head = node;
    // 在最后面插入一个节点
  } else if (index === this.length) {
    // 找到最后的元素
    const lastNode = this.getElementAt(this.length - 1);
    lastNode.next = node;
  } else {
    // 在中间位置插入元素
    // 找到之前index对应的元素的前一个元素
    const preNode = this.getElementAt(index - 1);
    // 找到当前元素
    const current = preNode.next;
    // 重新构建链表
    preNode.next = node;
    node.next = current;
  }
  // 修改链表长度
  this.length++;
  return true;
}

// + getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回undefined。
LinkedList.prototype.getElementAt = function (index) {
  // 处理下标越界
  if (index < 0 || index >= this.length) return null;
  let current = this.head;
  if (index === 0) return current;
  for (var i = 1; i < index; i++) {
    current = current.next;
  }
  return current;
}
// + remove(element)：从链表中移除一个元素，返回新链表的长度。
LinkedList.prototype.remove = function (node) {
  let current = this.head;
  // 如果移除的是head节点，则直接把head指向下一个节点
  if (current === node) {
    this.head = current.next;
    this.length--;
  }
  for (var i = 0; i < this.length; i++) {
    let preNode = current;
    current = current.next;
    // 如果是中间节点,则直接跳过当前节点
    if (current === node) {
      // 如果current是null,说明需要移除最后一个节点。
      preNode.next = current ? current.next : null;
      this.length--;
    }
  }
  // 最终返回删除元素后的新长度
  return this.length;
}
// + indexOf(node)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
LinkedList.prototype.indexOf = function (node) {
  let current = this.head;
  for (var i = 0; i < this.length; i++) {
    // TODO: 相等的条件是什么？
    // 这里使用元素node的地址做比较，当然我们可以自定义比较函数，那么需要在LinkedList构造函数传递
    if (current === node) {
      return i;
    }
    current = current.next;
  }
  return -1;
}

// + removeAt(index)：从链表的特定位置移除一个元素。
LinkedList.prototype.removeAt = function (index) {
  // 处理下标越界
  if (index < 0 || index >= this.length) return null;
  let current = this.head;
  // 移除第一项
  if (index === 0) {
    this.head = current.next;
  } else {
    // 如果不是第一项，则应该找到前面的节点和后面的节点
    preNode = this.getElementAt(index - 1);
    current = preNode.next;
    // 跳过当前元素.把当前元素去除，则应该preNode的next指向下一个元素
    preNode.next = current.next;
  }
  // 修改长度
  this.length--;
  // 返回被删除的元素本身
  return current.data;
}
// + isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
LinkedList.prototype.isEmpty = function () {
  return this.length === 0;
}

// + size()：返回链表包含的元素个数，与数组的length属性类似。
LinkedList.prototype.size = function () {
  return this.size() === 0;
}
// + toString()：返回表示整个链表的字符串。由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
LinkedList.prototype.toString = function () {
  let current = this.head;
  let str = '';
  while (current.next) {
    str += current.next.data + '';
    current = current.next;
  }
  return str;
}

function Node(data) {
  this.data = data;
  this.next = null;
}


module.exports = LinkedList;